#include <stdio.h>
#include <stdlib.h>

/* 链表 */
typedef struct _Node
{
    int data;
    struct _Node *prev;
    struct _Node *next;
} Node;
typedef Node List;

void initList(List *list)
{
    list->prev = list;
    list->next = list;
}

void addBack(List *list, int data)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = data;

    p->next = list;
    p->prev = list->prev;
    list->prev->next = p;
    list->prev = p;
}

void removeNode(Node *p)
{
    p->next->prev = p->prev;
    p->prev->next = p->next;
    free(p);
}

int isEmptyList(List *list)
{
    return list == list->next && list == list->prev;
}

int getListSize(List *list)
{
    int n = 0;
    for (Node *p = list->next; p != list; p = p->next) {
        n++;
    }
    return n;
}

void removeList(List *list)
{
    while (!isEmptyList(list)) {
        removeNode(list->prev);
    }
}

/* 队列 */
typedef struct {
    List list;
} Queue;

void initQueue(Queue *q)
{
    initList(&q->list);
}

int isEmptyQueue(Queue *q)
{
    return isEmptyList(&q->list);
}

void pushQueue(Queue *q, int data)
{
    addBack(&q->list, data);
}

void popQueue(Queue *q)
{
    if (!isEmptyQueue(q)) {
        removeNode(q->list.next);
    }
}

int getQueueTop(Queue *q)
{
    if (!isEmptyQueue(q)) {
        return q->list.next->data;
    } else {
        return -1;
    }
}

int getQueueSize(Queue *q)
{
    return getListSize(&q->list);
}

void showQueue(Queue *q)
{
    List *list = &q->list;
    printf("Size:%d Data:", getListSize(list));
    printf("<-");
    for (Node *p = list->next; p != list; p = p->next) {
        printf(" %d", p->data);
    }
    printf(" <-\n");
}

void removeQueue(Queue *q)
{
    removeList(&q->list);
}

void testQueue(void)
{
    Queue q;
    initQueue(&q);

    pushQueue(&q, 10);
    pushQueue(&q, 20);
    pushQueue(&q, 20);
    showQueue(&q);
    popQueue(&q);
    showQueue(&q);
    removeQueue(&q);

    for (int i = 0; i < 10; i++) {
        pushQueue(&q, i);
    }
    showQueue(&q);
    popQueue(&q);
    showQueue(&q);
    removeQueue(&q);
}

int main(int argc, char *argv[])
{
    testQueue();
    return 0;
}
